COMMENT ⊗   VALID 00003 PAGES 
RECORD PAGE   DESCRIPTION
 00001 00001
 00002 00002	4.0	MEMORY  -  DATA STRUCTURES.
 00004 00003	4.1	The Winged Edge Polyhedron Representation.
 00010 ENDMK
⊗;
4.0	MEMORY  -  DATA STRUCTURES.

	4.0	Introduction.
	4.1	The Winged Edge Polyhedron Representation.
	4.2	Three Image Representations: Video, FEV and CRE.
	4.3	Representation of a 3-D Mental Universe.
	4.4	Other Geometric Entities.
	4.5	GEOMED Node Formats.
	4.6	CRE Node Formats.
	4.7	Critique.

4.0	Introduction.

	In order to get a computer to deal with the physical world it
must  have  a  data representation  on  which  computations involving
space, time, shape, size and the appearance of things can be done. In
this  chapter,  a  particular representation  for  physical  objects,
images and  associated entities is explained. The data structures has
been implemented  as small  blocks of words  containing pointers  and
data in the fashion usual to graphics and simulation; an introduction
to this  technology  can  be  found in  Knuth.  Although  the  latest
language of implementation  is PDP-10 machine code,  earlier versions
were coded in LISP and SAIL with LEAP.
4.1	The Winged Edge Polyhedron Representation.

	A polyhedron  in  made up  of four  kinds  of nodes:  bodies,
faces, edges and  vertices. The body node is the head of three rings:
a ring of faces, a  ring of edges and  a ring of vertices. Each  face
and each  vertex points at  one of the  edges on its  perimeter. Each
edge  points at its  two faces  and its two  vertices. Completing the
structure, each  edge  node  contains a  link  to  each of  its  four
immediate  neighboring edges clockwise  and counter  clockwise around
face (vertex) perimeters. These last  four pointers are the wings  of
the edge,   which  provide the  basis for  efficient face and  vertex
perimeter  accessing.   Finally,the links  of the  edge nodes  can be
ordered in a consistent fashion over the surface of any polyhedron so
that the  surface always has two  sides: the inside and  the outside.
Klein bottles and worse are precluded by the data structure.

	Observe that  there are twenty-two  link fields in  the basic
representation: bodies contain six links, faces three, vertices three
and edges ten. Thus the least number of different link field names we
need to  coin is ten; if  we warn the  reader in advance that  a link
name such  as PED has different roles depending on whether it applies
to a body, face, edge or vertex.

---------------------------------------------------------------------
TABLE	   Data Structure			Link Names

   	1. Face Ring of a Body.			NFACE	PACE
	2. Edge Ring of a Body.			NED	PED
 	3. Vertex Ring of a Body.		NVT	PVT

	4. First Edge of a Vertex.			PED
	5. First Edge of a Face.			PED

	6. The two faces of an edge:		NFACE	PFACE
	7. The two vertices of an edge:		NVT	PVT
	8. The four wing edges of an edge:	NCW	PCW
						NCCW	PCCW
---------------------------------------------------------------------
FIGURE - THE WINGED EDGE.

	(As viewed from the exterior of a solid).

			\	  /
		 NCCW(E) \	 / PCW(E)
	                  \     /
	                   \   /      
	                    \ /
	                     ⊗ PVT(E)
	                     |
                             | 
               NFACE(E)      E         PFACE(E)
	                     |
	                     |
	              NVT(E) ⊗
	                    / \
	                   /   \        
	                  /     \
		  NCW(E) /	 \ PCCW(E)
			/	  \

	A face,   edge or vertex can only  belong to one body  and so
there is only one body node in a given face, edge or vertex ring; and
that body node serves as the head of the ring. The reason  for double
pointer rings is  for the sake of rapid deletion,  which allows local
alterations to a polyhedron's topology without any list searching.

	As  figure 2.2  suggests,  four of  these eight  pointers are
stored in the same positions and referred to by the same names as the
face and vertex  ring pointers; namely the NFACE,  PFACE, NVT and PVT
pointers.

	There are four ways in  which a pair of  faces and a pair  of
vertices can  be placed into  the two face  positions and  two vertex
positions  of  an  edge.  By  constraining  these choices  edges  can
independently  indicate  both  a  linear  direction  and   a  surface
orientation.

	The single winged edge pointer found in faces and vertices is
kept  in the  position named PED  and it points  to one  of the edges
belonging to that face or vertex. Although the vertices in figure 2.2
are shown  with three edges, vertices  may have any  number of edges;
those other potential edges would not be directly connected to E  and
so were not shown.